//
//  Code5.swift
//  cnswift-demo
//
//  Created by YangWei on 2021/1/10.
//  Copyright © 2021 YangWei. All rights reserved.
//

import UIKit


class Code5: Base {
    func run() {
//        runCase(inputStr: "babad", returnStr: ["bab", "aba"])
//        runCase(inputStr: "cbbd", returnStr: ["bb"])
//        runCase(inputStr: "a", returnStr: ["a"])
//        runCase(inputStr: "ac", returnStr: ["a", "c"])
//        runCase(inputStr: "ccc", returnStr: ["ccc"])
//        runCase(inputStr: "aaaa", returnStr: ["aaaa"])
//        runCase(inputStr: "abcba", returnStr: ["abcba"])
//        runCase(inputStr: "abcdcba123", returnStr: ["abcdcba"])
//        runCase(inputStr: "aacabdkacaa", returnStr: ["aca"])
//        runCase(inputStr: "aaabcba", returnStr: ["abcba"])
        runCase(inputStr: "xaabacxcabaaxcabaax", returnStr: ["xaabacxcabaax"])
    }
    
    func runCase(inputStr: String, returnStr: [String]) {
        let result = longestPalindrome(inputStr)
        if returnStr.contains(result) {
            print("✅ \(inputStr) 的回文字符串是 \(result)")
        }
        else {
            print("❌ \(inputStr) 的回文字符串不是 \(result)")
        }
    }
    
    func longestPalindrome(_ s: String) -> String {
        var resultStr = ""
        var palindromeStr = ""
        var maxLength = 0
        
        if s.count >= 1 {
            palindromeStr = String(s[(s.startIndex)...(s.startIndex
                )])
            maxLength = 1
        }
        
        for char in s {
            if resultStr.contains(char) {
                let fistIndex = resultStr.firstIndex(of: char)
                
                var endIndex = resultStr.index(before: resultStr.endIndex)
                
                func judgeStr(subStr:String, beginIndex: String.Index) -> Bool {
                    endIndex = resultStr.index(before: resultStr.endIndex)
                    
                    let isPalindrome = checkIsAPalindromeStr(subStr)
                    
                    if isPalindrome {
                        // 匹配回文字符串
                        if subStr.count > maxLength {
                            palindromeStr = subStr
                            maxLength = subStr.count
                        }
                    }
                    else {
                        let resetBeginIndex = resultStr.index(after: beginIndex)
                        resultStr = String(resultStr[resetBeginIndex...endIndex])
                    }
                    return isPalindrome
                }
                
                var subStr = String( resultStr[fistIndex!...endIndex])
                subStr.append(char)
                if judgeStr(subStr: subStr, beginIndex: fistIndex!) {
                    // 检查最前面的匹配
                    resultStr.append(char)
                    continue
                }
                
                endIndex = resultStr.index(before: resultStr.endIndex)
                var nextIndex = resultStr.firstIndex(of: char)
                var findAResult = false
                
                while nextIndex != nil && nextIndex != endIndex {
                    
                    subStr = String(resultStr[nextIndex!...endIndex])
                    subStr.append(char)
                    
                    if judgeStr(subStr: subStr, beginIndex: nextIndex!) {
                        resultStr.append(char)
                        findAResult = true
                        break
                    }
                    
                    nextIndex = resultStr.firstIndex(of: char)
                    endIndex = resultStr.index(before: resultStr.endIndex)
                }
                
                if findAResult {
                    continue
                }
                
                resultStr.append(char)
                
            } else {
                resultStr.append(char)
            }
        }
        
        return palindromeStr
    }
    
    func checkIsAPalindromeStr(_ s: String) -> Bool {
        print("check \(s)")
        
        let strCount = s.count
        
        if s.count <= 1 {
            return true
        }
        
        for i in 0..<(strCount/2) {
            let firstStartIndex = s.index(s.startIndex, offsetBy: i)
            let secondStartIndex = s.index(before: s.index(s.endIndex, offsetBy: -i))
            if s[firstStartIndex...firstStartIndex] == s[secondStartIndex...secondStartIndex] {
                continue
            } else {
                return false
            }
        }
        return true
    }
}
